package goleetcode

import "duan.com/leetcode/utils"

/*
	将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。
	这样我们只需要反序中序遍历该二叉搜索树，记录过程中的节点值之和
	并不断更新当前遍历到的节点的节点值
*/
func bstToGst(root *utils.TreeNode) *utils.TreeNode {
	sum := 0
	var dfs func(*utils.TreeNode)
	dfs = func(node *utils.TreeNode) {
		if node != nil {
			dfs(node.Right)
			sum += node.Val
			node.Val = sum
			dfs(node.Left)
		}
	}
	dfs(root)
	return root
}